//给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。 
//
// 每一步，你可以从下标 i 跳到下标： 
//
// 
// i + 1 满足：i + 1 < arr.length 
// i - 1 满足：i - 1 >= 0 
// j 满足：arr[i] == arr[j] 且 i != j 
// 
//
// 请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。 
//
// 注意：任何时候你都不能跳到数组外面。 
//
// 
//
// 示例 1： 
//
// 输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
//输出：3
//解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。
// 
//
// 示例 2： 
//
// 输入：arr = [7]
//输出：0
//解释：一开始就在最后一个元素处，所以你不需要跳跃。
// 
//
// 示例 3： 
//
// 输入：arr = [7,6,9,6,9,6,9,7]
//输出：1
//解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。
// 
//
// 示例 4： 
//
// 输入：arr = [6,1,9]
//输出：2
// 
//
// 示例 5： 
//
// 输入：arr = [11,22,7,7,7,7,7,7,7,22,13]
//输出：3
// 
//
// 
//
// 提示： 
//
// 
// 1 <= arr.length <= 5 * 10^4 
// -10^8 <= arr[i] <= 10^8 
// 
// Related Topics 广度优先搜索 数组 哈希表 👍 99 👎 0

package com.cute.leetcode.editor.cn;

import java.util.*;

public class JumpGameIv {
    public static void main(String[] args) {
        int[] arr = {100,-23,-23,404,100,23,23,23,3,404};
        new JumpGameIv().new Solution().minJumps(arr);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 最短路径问题，使用BFS去做
         * 说实话看题解也是云里雾里的
         * 当前位置的前、后、同值位置的时候只有在没访问过的时候才会进行入队及步数的更新
         */
        public int minJumps(int[] arr) {
            int len = arr.length;
            int INF = len + 1;
            Map<Integer, List<Integer>> map = new HashMap<>();//使用map来记录可以同值跳跃的下标
            for (int i = len - 1; i >= 0 ; i--) {//倒叙添加的，保证下标越大，越优先出队
                List<Integer> list = map.getOrDefault(arr[i], new ArrayList<>());
                list.add(i);
                map.put(arr[i],list);
            }
            int[] dist = new int[len];//存储最小步数
            Arrays.fill(dist, INF);
            Deque<Integer> queue = new ArrayDeque<>();//创建BFS队列，存储下标
            dist[0] = 0;
            queue.addLast(0);
            while (!queue.isEmpty()){
                int t = queue.pollFirst(), step = dist[t];
                if (t == len-1) return step;//这里说明到达了最后一个位置，直接返回
                if (t + 1 < len && dist[t + 1] == INF){
                    queue.addLast(t + 1);
                    dist[t + 1] = step + 1;
                }
                if (t - 1 >= 0 && dist[t - 1] == INF){
                    queue.addLast(t - 1);
                    dist[t - 1] = step + 1;
                }
                List<Integer> list = map.getOrDefault(arr[t], new ArrayList<>());//这里要有缺省值，否则可能会报错的
                for (int same : list){//遍历所有同值位置
                    if (dist[same] == INF){
                        queue.addLast(same);
                        dist[same] = step + 1;
                    }
                }
                map.remove(arr[t]);//防止重复同值赋值，删除所有下标，这里是可以证明合理的
            }
            return -1;//不会达到
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}